using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
// isMaxNr==true to że jest ograniczenie dla liczby wierzchołków w jednym kolorze i wtedy maxNr jest tym ograniczeniem
//isMaxNr==false to że nie ma żadnego ograniczenia
namespace az
{
    class DSatur
    {
        public void DStaturAlgoritm(Graph graph, bool isMaxNr, int maxNr)
        {
            int n = graph.countVertex;
            if (n <= 0)
                return;
            List<Vertex> temp = null;
            foreach (Vertex v in graph.listVertex)
                v.numberColor = 0;
            if (isMaxNr)
            {
                int[] used_count = new int[graph.countVertex + 1];
                for (int j = 0; j < n; j++)
                {
                    int[] used_neigh = new int[n + 1];
                    int maxsatur = 0;
                    int satur = 0;
                    Vertex current = null;
                    //szukam kolejnego wierzcholka
                    foreach (Vertex v in graph.listVertex)
                    {
                        if (v.numberColor > 0)
                            continue;
                        satur = 0;
                        temp = v.listVertexNeighbor;
                        //licze stopien saturacyjny
                        foreach (Vertex v2 in temp)
                        {
                            if (used_neigh[v2.numberColor] != v.number)
                            {
                                satur++;
                                used_neigh[v2.numberColor] = v.number;
                            }
                        }
                        if (current == null || satur > maxsatur || (satur == maxsatur && current.countVertexNeighbour < v.countVertexNeighbour))
                        {
                            maxsatur = satur;
                            current = v;
                        }
                    }
                    temp = current.listVertexNeighbor;
                    //sprawdzam kolory sasiadow
                    foreach (Vertex v in temp)
                        used_neigh[v.numberColor] = current.number;
                    //kolouje zachlannie
                    for (int i = 1; i <= n; i++)
                    {
                        if (used_count[i] < maxNr && used_neigh[i] != current.number)
                        {
                            current.numberColor = i;
                            used_count[i]++;
                            break;
                        }
                    }
                }
            }
            else
            {
                //int[] used_count = new int[graph.countVertex + 1];
                for (int j = 0; j < n; j++)
                {
                    int[] used_neigh = new int[n + 1];
                    for (int i = 0; i < n + 1; i++)
                        used_neigh[i] = 0;
                    int maxsatur = 0;
                    int satur = 0;
                    Vertex current = null;
                    foreach (Vertex v in graph.listVertex)
                    {
                        if (v.numberColor > 0)
                            continue;
                        satur = 0;
                        temp = v.listVertexNeighbor;
                        foreach (Vertex v2 in temp)
                        {
                            if (used_neigh[v2.numberColor] != v.number)
                            {
                                satur++;
                                used_neigh[v2.numberColor] = v.number;
                            }
                        }
                        if (current == null || satur > maxsatur || (satur == maxsatur && current.countVertexNeighbour < v.countVertexNeighbour))
                        {
                            maxsatur = satur;
                            current = v;
                        }
                    }
                    temp = current.listVertexNeighbor;
                    foreach (Vertex v in temp)
                        used_neigh[v.numberColor] = current.number;
                    for (int i = 1; i <= n; i++)
                    {
                        if (/*used_count[i] < maxNr &&*/ used_neigh[i] != current.number)
                        {
                            current.numberColor = i;
                            //used_count[i]++;
                            break;
                        }
                    }
                }
            }

        }
    }
    

}
